package TAIC.Classifier;

import java.io.File;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.Vector;

import TAIC.kdtree.KDTree;

public class KNN extends Classifier {
	KDTree kdtree = null ;
	int maxIndex = 0 ;
	int maxClass = 0 ; 
	int K = 0 ; 
	
	public static void main ( String args[ ]) throws Exception {
		if ( args.length != 3 ) {
			System.out.println ( "please input the K, trainingFile and testFile") ;
			return ;
		}
		int k = Integer.valueOf( args[ 0 ] ) ;
		KNN knn = new KNN ( k ) ;
		knn.train( args[ 1 ]) ;
		double result = knn.test ( args[ 2 ]) ;
		System.out.printf( "Accuracy = %f%%", result) ;
	}
	
	
	public KNN ( int K ){
		this.K =  K ;
	}
	
	public void train(String trainFile) {
		try{
			Vector < Instance > data = new Vector< Instance > () ;
			Scanner scanner = new Scanner ( new File (trainFile )) ;
			while ( scanner.hasNextInt() ) {
				Instance ins = getInstance ( scanner.nextLine() ) ;
				if ( ins.get(ins.size()-1).index  > maxIndex ) maxIndex = ins.get(ins.size()-1).index ;
				if ( ins.classNo  > maxClass ) maxClass = ins.classNo ;
				data.add( ins ) ;
			}
			scanner.close() ;

			maxIndex ++ ;
			maxClass ++ ;
			kdtree = new KDTree < Integer > ( maxIndex ) ;
			double[]  arr = new double [ maxIndex ] ; 
			for ( int i = 0 ; i < data.size() ; i ++ 	) {
				try {
					Arrays.fill( arr , 0) ;
					for ( Node n : data.get(i) ) arr[n.index] = n.value ;
					kdtree.insert( arr , data.get(i).classNo ) ;
				}catch( Exception e){}
			}
		}catch ( Exception e ) {}
	}

	public double test(String testFile) {
		try {
			PrintStream fout = new PrintStream ( new File ( "predict.txt" )) ;
			Scanner scanner = new Scanner ( new File( testFile )) ;
			double[]  arr = new double [ maxIndex ] ;
			int correct = 0 ;
			int total = 0 ;
			int count [] = new int [ maxClass ] ;
			while ( scanner.hasNextInt() ) { 
				Arrays.fill(arr, 0) ;
				Arrays.fill(count, 0) ;
				Instance ins = getInstance ( scanner.nextLine() ) ;
				for ( Node n  : ins ) arr[ n.index ] = n.value ;
				List<Integer> result = kdtree.nearest( arr, K ) ;
				for ( Integer i : result ) count [ i ] ++ ;
				int max = 0 ;
				int label = 0 ;
				for ( int i = 0 ; i < maxClass; i ++ ) 
					if ( max < count [ i ] ) {
						max = count[ i ] ;
						label = i ; 
					}
				fout.println( label );
				if ( label == ins.classNo ) correct ++ ;
				total ++ ;
			}
			fout.close() ;
			scanner.close() ;
//			System.out.println ( correct / (double)total ) ;
			return correct / (double)total;
		}catch ( Exception e ) {}
		return -1;
	}
	
	public boolean isPipe() {
		return false ; 
	}

	Instance getInstance ( String str ) {
		Scanner strScanner = new Scanner ( str ) ;
		int classNo = strScanner.nextInt() ; 
		Instance instance = new Instance ( classNo ) ; 
		while ( strScanner.hasNext() ) {
			String tmp = strScanner.next() ;
			int pos = tmp.indexOf(':');
			int index = Integer.valueOf(tmp.substring(0, pos)) ;
			int value = Integer.valueOf(tmp.substring(pos+1)) ;
			instance.add( new Node(index,value)) ;
		}		
		strScanner.close() ;
		return instance ;
	}
	
}

class Node {
	public int index, value ;
	public Node ( int index, int value ) {
		this.index = index ;
		this.value = value ;
	}
}

class Instance implements Iterable< Node >{
	public int classNo ;
	public LinkedList < Node > data = new LinkedList < Node > () ;
	
	public Instance ( int c ) {
		classNo = c ;
	}

	public void add ( Node n ) {
		data.add( n ) ; 
	}
	
	public int size () {
		return data.size ();
	}
	
	public Node get ( int index ) {
		return data.get(index) ;
	}
	
	public Iterator<Node> iterator() {
		return data.iterator();
	}
}